// https://leetcode.cn/problems/split-array-with-same-average/
// Created by ade on 2022/11/14.
// 我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average(A) == average(B) 。
// 输入: nums = [1,2,3,4,5,6,7,8]
//输出: true
//解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

class Solution {
public:
    bool splitArraySameAverage(vector<int> &nums) {
        int count = nums.size();
        if (count <= 1) return false;
        int sum = accumulate(nums.begin(), nums.end(), 0);

        for (auto &i:nums) {
            i = i * count - sum;
            if (i == 0) return true;
        }
        int mid = count / 2;
        unordered_set<int> mySet = {};
        for (int i = 1; i < (1 << mid); i++) {
            int total = 0;
            for (int j = 0; j < mid; j++) {
                if (i & (1 << j)) {
                    total += nums[j];
                }
            }
            if (total == 0) return true;
            mySet.insert(total);
        }
        int rSum = accumulate(nums.begin() + mid, nums.end(), 0); // 这里防止所有的值相加为0 的情况。
        for (int i = 1; i < (1 << count - mid); i++) {
            int total = 0;
            for (int j = mid; j < count; j++) {
                if (i & (1 << (j - mid))) {
                    total += nums[j];
                }
            }
            if (total == 0 || rSum != total && mySet.count(-total)) {
                return true;
            }
        }

        return false;
    }
};

int main() {
    Solution so;
    vector<int> nums = {10, 29, 13, 53, 33, 48, 76, 70, 5, 5};
    cout << so.splitArraySameAverage(nums) << endl;
    return 0;
}